package com.cx.algrithm.sort.Heap;

/**
 * @Author: robert.song
 * @Date: Created in 2021/8/7
 */
public class HeapSort {
    //    判断heap堆中索引i处的元素是否小于索引j处的元素
    private static boolean less(Comparable[] heap, int i, int j) {

        return heap[i].compareTo(heap[j]) < 0;
    }

    //    交换heap堆中的i索引和j索引值
    private static void exch(Comparable[] heap, int i, int j) {
        Comparable tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }

    //    根据原数组source,构造heap
    private static void createHeap(Comparable[] source, Comparable[] heap) {
//        把source中元素拷贝到heap中，heap中元素就形成了一个无序的堆
        System.arraycopy(source, 0, heap, 1, source.length);
//        对堆中元素做下沉调整（从长度一半开始，往索引1处扫描）
        for (int i = (heap.length) / 2; i > 0; i--) {
            sink(heap, i, heap.length - 1);
        }
    }

    //    对source数组的数据从小到大排序
    public static void sort(Comparable[] source) {
//        构建堆
        Comparable[] heap = new Comparable[source.length + 1];
        createHeap(source, heap);
//        定义一个变量，记录未排序的元素中最大的索引
        int N = heap.length - 1;
//        通过循环，交换1索引处的元素和排序的元素中最大的索引处的元素
        while (N != 1) {
//            交换元素
            exch(heap, 1, N);
//            排序交换后最大元素所在的索引，让它不要参与堆的下沉结构
            N--;
//            需要对索引1处元素进行堆的下沉调整
            sink(heap, 1, N);
        }
//        把heap中的数据复制到原数组source中
        System.arraycopy(heap, 1, source, 0, source.length);

//        排序
    }

    //    在heap中，对target处的元素做下沉，发那位是0-range
    private static void sink(Comparable[] heap, int target, int range) {
        while (2 * target <= range) {
//            1、找出当前节点的较大子节点
            int max;
            if (less(heap, 2 * target, 2 * target + 1)) {
                max = 2 * target + 1;
            } else {
                max = 2 * target;
            }
//            2、比较当前节点值和较大子节点的值
            if (!less(heap, target, max)) {
                break;
            }

            exch(heap, target, max);

            target = max;
        }
    }
}
